#include <cstddef>
#include <stdexcept>

using namespace msl;

// ====================
// List Iterator
// ====================

// using typename List<T>::ListIterator;

template<typename T>
typename List<T>::ListElement* List<T>::ListIterator::getptrListElement() const {
    return this->el;
}

template<typename T>
List<T>::ListIterator::ListIterator() {
    // empty
}

template<typename T>
List<T>::ListIterator::ListIterator(List<T>::ListElement *ptr) : el(ptr) {
    // empty
}

template<typename T>
T& List<T>::ListIterator::operator*() const {
    return el->value;
}

template<typename T>
T* List<T>::ListIterator::operator->() {
    return &(el->value);
}

template<typename T>
typename List<T>::ListIterator& List<T>::ListIterator::operator++() {
    el = el->next;
    return *this;
}

template<typename T>
typename List<T>::ListIterator List<T>::ListIterator::operator++(int _) {
    typename List<T>::ListIterator old_it = *this;
    el = el->next;
    return old_it;
}

template<typename T>
typename List<T>::ListIterator& List<T>::ListIterator::operator--() {
    el = el->previous;
    return *this;
}

template<typename T>
typename List<T>::ListIterator List<T>::ListIterator::operator--(int _) {
    typename List<T>::ListIterator old_it = *this;
    el = el->previous;
    return old_it;
}

template<typename T>
bool List<T>::ListIterator::operator==(const typename List<T>::ListIterator& other) {
    return this->el == other.getptrListElement();
}

template<typename T>
bool List<T>::ListIterator::operator!=(const typename List<T>::ListIterator& other) {
    return this->el != other.getptrListElement();
}
 
// ====================
// List
// ====================

template<typename T>
List<T>::List() : head(NULL), tail(NULL) {
    // empty
}
 
template<typename T>   
List<T>::List(const List &other) : head(NULL), tail(NULL) {
    copy(other);
}

template<typename T>
List<T>::List(std::initializer_list<T> values) : head(NULL), tail(NULL) {
    head = NULL; tail = NULL;
    for(auto el: values) {
        push_back(el);
    }
}

template<typename T>
List<T>::~List() { 
    while(!this->empty()) this->pop_front();
}

template<typename T>
void List<T>::copy(const List<T> &other) {
    if(other.empty()) { head = NULL; tail = NULL; return; }
    ListElement *otail = other.head;
    ListElement *ttail = this->head = new ListElement{{}, NULL, NULL}; 
    ttail->value = otail->value;
    while(otail->next != NULL) { 
        ttail->next = new ListElement{{}, ttail, NULL};
        ttail = ttail->next;
        otail = otail->next;
        ttail->value = otail->value;
    }
    this->tail = ttail;
}

template<typename T>
List<T> List<T>::operator=(const List &other) {
    copy(other);
    return *this;
}

template<typename T>
typename List<T>::ListIterator List<T>::begin() {
    return ListIterator(this->head);
}

template<typename T>
typename List<T>::ListIterator List<T>::end() {
    return ListIterator(NULL);
}

template<typename T>
bool List<T>::empty() const {
    return head == NULL;
}

template<typename T>
void List<T>::clear() {
    while(!this->empty()) this->pop_front(); 
}

template<typename T>
T List<T>::get_front() const {
    if(this->empty()) throw std::runtime_error("Can't delete element from empty list");
    return this->head->value;
}

template<typename T>
T List<T>::get_back() const {
    if(this->empty()) throw std::runtime_error("Can't delete element from empty list");
    return this->tail->value;
}

template<typename T>
void List<T>::push_front(T el) {
    ListElement *old_head = this->head;
    this->head = new ListElement{el, NULL, old_head};
    if(this->tail == NULL) this->tail = this->head;
    else old_head->previous = this->head;
}

template<typename T>
void List<T>::push_back(T el) {
    ListElement *old_tail = this->tail;
    this->tail = new ListElement{el, old_tail, NULL};
    if(this->head == NULL) this->head = this->tail;
    else old_tail->next = this->tail;
}

template<typename T>
void List<T>::pop_front() {
    if(this->empty()) throw std::runtime_error("Can't delete element from empty list");
    ListElement *old_head = head->next;
    delete head;
    head = old_head;
    if(head == NULL) tail = NULL;
    else head->previous = NULL;
}

template<typename T>
void List<T>::pop_back() {
    if(this->empty()) throw std::runtime_error("Can't delete element from empty list");
    ListElement *old_tail = tail->previous;
    delete tail;
    tail = old_tail;
    if(tail == NULL) head = NULL;
    else tail->next = NULL;
}

template<typename T>
T List<T>::pullout_front() {
    T res = this->get_front();
    this->pop_front();
    return res;
}

template<typename T>
T List<T>::pullout_back() {
    T res = this->get_back();
    this->pop_back();
    return res;
}

template<typename T>
void List<T>::insert(typename List<T>::ListIterator it, T value) {
    if(it == this->end()) { 
        ListElement *new_el = new ListElement{value, this->tail, NULL};
        this->tail->next = new_el;
        this->tail = new_el;
    }
    else if(it == this->begin()) {
        ListElement *new_el = new ListElement{value, NULL, this->head};
        this->head->previous = new_el;
        this->head = new_el;
    }
    else {
        ListElement *el = it.getptrListElement();
        ListElement *new_el = new ListElement{value, el->previous, el};
        el->previous->next = new_el;
        el->previous = new_el;
    }
}

template<typename T>
void List<T>::erase(typename List<T>::ListIterator it) {
    if(it == this->end()) throw std::runtime_error("Can't delete non-existent element");
    ListElement *el = it.getptrListElement();
    ListElement *lel = el->previous, *rel = el->next;

    if(lel != NULL) lel->next = rel;
    else this->head = rel;
    if(rel != NULL) rel->previous = lel;
    else this->tail = lel;
    
    delete el;
}

template<typename T>
void List<T>::erase(typename List<T>::ListIterator lit, typename List<T>::ListIterator rit) {
    if(lit == this->end()) throw std::runtime_error("Can't delete range with non-existent element");
    ListElement *lel = lit.getptrListElement(), *rel = rit.getptrListElement();
    for(ListElement *el = lel; el != rel; el = el->next) 
        if(el == NULL) throw std::runtime_error("Incorrect arguments");

    if(lel->previous != NULL) lel->previous->next = rel;
    else this->head = rel;
    if(rel != NULL) rel->previous = lel->previous;
    else this->tail = lel->previous;
    
    for(ListElement *el = lel; el != rel; el = el->next) {
        delete el;
    }
}

